﻿// E.Binary String - 1680C.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
https://codeforces.com/problemset/problem/1680/C

题意
给定一个01串，可以删除不定长度的左侧连续字符，或不定长度的右侧连续字符。
换句话说，就是截取一段连续的字符串保留下来，左右两边都剔除掉。

问怎样删除使得留下的0的数量和删除的1的数量的两者的最大值最小，求这个最小值。

思路（双指针）
我们记c0​ :保留下来的0的个数，
c1​:删除掉的1的个数。

对于一段区间[l,r]，当l确定后，r增加，过程中c0递增，c1 递减，
且有一个特点c1c0不会同时进行递增/递减，必然是一个递增/递减，一个不变，
也就意味着必然存在一个点使得两者的值相等（他们的变化在整数范围内看做是连续的），而不会擦肩而过。

假设到r=k时有c0=c1，此时一定为最优方案，r再往右走已经没有意义了。
也就是说，对于左端点l，有一个对应的最优右端点k使得结果最小。

现在来证明
[l+1,t],t<k 不会比
[l+1,k] 更好，因为左端点右移，区间变小，
c0变小或不变，c1变大或不变，于是c0和c1 的差距又被拉开了，为了达到c0 =c1​
l+1所对应的k肯定比l对应的k更靠右或相等。

于是l右移后，右端点r无需重置，只需要继续往右走即可。

在移动过程中动态维护c0,c1即可。

代码（双指针）

思路（数学法）
01串问题经常和前缀和联系起来，我们先对其进行一个前缀和。

于是只需要枚举r，即可直接算出l，对每个区间计算结果取小即可。

给您一个由字符 0 和/或 1 组成的字符串 s。

您必须从字符串的开头删除几个（可能是零）字符，然后从字符串的结尾删除几个（可能是零）字符。删除后，字符串可能为空。
删除的代价是以下两个值的最大值：

字符串中剩余的字符数 0；
从字符串中删除的字符数 1。
你能达到的最小删除成本是多少？

输入
第一行包含一个整数 t（1≤t≤104）--测试用例数。

每个测试用例包含一行字符串 s (1≤|s|≤2⋅105)，由字符 0 和/或 1 组成。

字符串 s 的总长度不超过 2⋅105。

输出

Example
InputCopy
5
101110110
1001001001001
0000111111
00000
1111
OutputCopy
1
3
0
0
0

注释
请看示例中的测试用例：

在第一个测试用例中，可以从开头删除两个字符，从结尾删除一个字符。只删除一个 1，只保留一个 0，所以代价是 1；
在第二个测试案例中，可以从开头删除三个字符，从结尾删除六个字符。两个字符 0 保留，三个字符 1 删除，因此代价是 3；
在第三个测试案例中，最好从开头删除四个字符；
在第四个测试案例中，最好删除整个字符串；
在第五个测试案例中，保持字符串原样是最佳选择。
*/

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;


//in0  线段里0的个数
//out1 外面1的个数
//扩大范围 要么0增加 要么1减少
//减少范围 要么0减少 要么1增加
int T;
string str;

/*
void solve() {
	cin >> str;

	int l = 0; int r = 0;
	int in0 = 0; int out1 = 0;
	if (str[l] == '0') in0 = 1;
	for (int i = 1; i < str.size(); i++) {
		if (str[i] == '1') out1++;
	}
	int ans = 0x3f3f3f3f;
	if (in0 == out1) {
		ans = min(ans, in0);
	}
	while (l < str.size() && r < str.size()) {
		//cout << "l = " << l << ". r = " << r << ". in0 = " << in0 << ". out1 = " << out1 << endl;
		if (in0 < out1) {
			r++;
			if (str[r] == '0') {
				in0++;
			}
			else if (str[r] == '1') {
				out1--;
			}
		}
		else if(in0 >= out1){
			if (str[l] == '0') {
				in0--;
			}
			else if (str[l] == '1') {
				out1++;
			}
			l++;
		}
		if (in0 == out1) {
			ans = min(ans, in0);
		}
	}
	//if (ans == 0x3f3f3f3f) ans = 0;
	cout << ans << endl;
}
*/

const int N = 200010;
int pre[N];

void solve() {
	memset(pre, 0, sizeof pre);
	cin >> str;
	str.insert(str.begin(), '#');
	for (int i = 1; i < str.size(); i++){
		pre[i] = pre[i - 1] + (str[i] - '0');
	}
	int ans = 0x3f3f3f3f;
	for (int r = 1; r < str.size(); r++) {
		int l = r + 1 - pre[str.size() - 1];
		if(l <= 0) continue;
		ans = min(ans,r - l + 1 -( pre[r] - pre[l - 1]));
	}

	cout << ans << endl;
	return;
}

int main()
{
	cin >> T;
	while (T--) {
		solve();
	}

	return 0;
}

